package com.chl.sort.other;

/**
 * 希尔排序 - 不稳定
 * 
 * 核心
 * 		平均分组、插入排序
 * 
 * 算法描述
 * 		选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 		按增量序列个数k，对序列进行k 趟排序；
 * 		每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
 * 		仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 * 
 * @author 陈宏亮
 *
 */
public class Sort06Shell {
	public static void sort(int[] arrs) {
		int g, i, j, l = arrs.length;
	    int tmp;
	    for (g = l >> 1; g > 0; g >>= 1) {
	    	// 把每个划分组的第0个元素当成已排序列，从每个划分组第1个元素开始比较。
	    	// [第0划分组第0个, 第1划分组第0个, 第2划分组第0个...第0划分组第1个, 第1划分组第1个, 第2划分组第1个...第0划分组第2个, 第1划分组第2个, 第2划分组第2个......] 
	        for (i = g; i < l; i++) {
	            tmp = arrs[i];
	            // 寻找位置并移动元素
	            for (j = i - g; j >= 0 && arrs[j] > tmp; j -= g)
	                arrs[j + g] = arrs[j];
	            arrs[j + g] = tmp;
	        }
	    }
	}

	public static void shell_sort(int[] arr) {
		int g = 1, i, j, l = arr.length;
		int temp;
		while (g < l / 3)
			g = g * 3 + 1;
		for (; g > 0; g /= 3) {
			for (i = g; i < l; i++) {
				temp = arr[i];
				for (j = i - g; j >= 0 && arr[j] > temp; j -= g)
					arr[j + g] = arr[j];
				arr[j + g] = temp;
			}
		}
	}
}
